字符串处理——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

对字符串进行拼接、匹配、编码等操作，目标是最小化拼接代价、最大化匹配效率，每一步选择当前最优的字符串操作策略。

本教程以多个字符串处理贪心算法案例场景为例，让大家彻底理解以 “局部最优” 推导 “全局最优” 的核心逻辑，并掌握最优字符串拼接、贪心匹配算法的原理及代码实现。

最优字符串拼接：给定多个字符串，拼接成一个总字符串，最小化拼接时的总代价（如拼接两个长度为 m、n 的字符串代价为 m+n），策略是每次选择长度最短的两个字符串拼接（与哈夫曼树思想一致）。实际场景：大数据文件的合并（最小化磁盘 IO 次数）、字符串数组的拼接优化。
贪心匹配算法：在字符串匹配中（如 KMP 的简化版、正则表达式的简单匹配），按从左到右优先匹配最长 / 最短子串的策略，快速完成匹配。实际场景：文本检索的关键词匹配、编辑器的查找替换功能。

教程目录导航

▼

排序问题
- 一、最优字符串拼接
- 二、贪心匹配算法

一、最优字符串拼接

问题描述：

给你两个字符串 word1 和 word2 。你需要按下述方式构造一个新字符串 merge ：如果 word1 或 word2 非空，选择下面选项之一继续操作：
1. 如果 word1 非空，将 word1 中的第一个字符附加到 merge 的末尾，并将其从 word1 中移除。
  例如，word1 = "abc" 且 merge = "dv" ，在执行此选项操作之后，word1 = "bc" ，同时 merge = "dva" 。
2. 如果 word2 非空，将 word2 中的第一个字符附加到 merge 的末尾，并将其从 word2 中移除。
  例如，word2 = "abc" 且 merge = "" ，在执行此选项操作之后，word2 = "bc" ，同时 merge = "a" 。
3. 比较word1和word2字典序大小，如果 word1 中的第一个字符在 word2 中的第一个字符的字典序之后，就认为字符串 word1 按字典序比字符串 word2 更大。那么就将 word1 中的第一个字符附加到 merge 的末尾，并将其从 word1 中移除。
  例如，word1 = "cab"和word2 = "abc" 且 merge = "" ，在执行此选项操作之后，word1 = "ab" ，同时 merge = "c"，word2 = "abc" 。
word1 和 word2 仅由小写英文组成
1 <= word1.length, word2.length <= 3000

示例：

输入：word1 = "cabaa", word2 = "bcaaa"
输出："cbcabaaaaa"
解释：构造字典序最大的合并字符串，可行的一种方法如下所示：
- 从 word1 中取第一个字符：merge = "c"，word1 = "abaa"，word2 = "bcaaa"
- 从 word2 中取第一个字符：merge = "cb"，word1 = "abaa"，word2 = "caaa"
- 从 word2 中取第一个字符：merge = "cbc"，word1 = "abaa"，word2 = "aaa"
- 从 word1 中取第一个字符：merge = "cbca"，word1 = "baa"，word2 = "aaa"
- 从 word1 中取第一个字符：merge = "cbcab"，word1 = "aa"，word2 = "aaa"
- 将 word1 和 word2 中剩下的 5 个 a 附加到 merge 的末尾。

算法解析：

假设当前需要从 word 1的第 i 个字符和 word 2的第 j 个字符选择一个字符加入到新字符串 merge 中，需要进行分类讨论:
- 如果 word1[i] > word2[j]，此时我们的最优选择是移除 word1[i] 加入到 merge 中，从而保证 merge 的字典序最大；
- 如果 word1[i] < word2[j]，此时我们的最优选择是移除 word2[j] 加入到 merge，从而保证 merge 的字典序最大；
- 如果 word1[i] == word2[j]，此时则需要进一步讨论，结论如下：
  - 如果 word1 从 i 开始的后缀字典序大于 word2 从 j 开始的后缀，则此时优先选择移除 word1[i] 加入到 merge 中；
  - 如果 word1 从 i 开始的后缀字典序小于 word2 从 j 开始的后缀，则此时优先选择移除 word2[i] 加入到 merge 中；
  - 如果 word1 从 i 开始的后缀字典序等于 word2 从 j 开始的后缀，则此时任选一个均可；


#include <iostream>
using namespace std;

char* largestMerge(char * word1, char * word2) {
    int m = strlen(word1), n = strlen(word2);
    char *merge = (char *)malloc(sizeof(char) * (m + n + 1));
    int i = 0, j = 0, pos = 0;
    while (i < m || j < n) {
        if (i < m && strcmp(word1 + i, word2 + j) > 0) {
            merge[pos] = word1[i];
            pos++, i++;
        } else {
            merge[pos] = word2[j];
            pos++, j++;
        }
    }
    merge[pos] = '\0';
    return merge;
}

int main() {
    char* word1="cabaa";
    char* word2="bcaaa";

    cout << "word1=" << word1 << endl;
    cout << "word2=" << word2 << endl;
    cout << "merge=" << largestMerge(word1, word2);

    return 0;
}

输出结果


word1=cabaa
word2=bcaaa
merge=cbcabaaaaa

二、贪心匹配算法

问题描述：

给你一个字符串 time ，格式为 hh:mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。
有效的时间为 00:00 到 23:59 之间的所有时间，包括 00:00 和 23:59 。
替换 time 中隐藏的数字，返回你可以得到的最晚有效时间。

示例1：

输入：time = "2?:?0"
输出："23:50"
解释：以数字 '2' 开头的最晚一小时是 23 ，以 '0' 结尾的最晚一分钟是 50 。

示例2：

输入：time = "0?:3?"
输出："09:39"

示例2：

输入：time = "1?:22"
输出："19:22"

算法解析：

为了得到最晚有效时间，我们可以从高位向低位枚举，在保证时间有效的情况下，使得每一位尽可能取最大值。

第一位：若第二位的值已经确定，且值落在区间 [4,9] 中时，第一位的值最大只能为 1，否则最大可以为 2；
第二位：若第一位的值已经确定，且值为 2 时，第二位的值最大为 3，否则为 9；
第三位：第三位的值的选取与其它位无关，最大为 5；
第四位：第四位的值的选取与其它位无关，最大为 9。


#include <iostream>

using namespace std;

char* maximumTime(char* time) {
    if (time[0] == '?') {
        time[0] = ('4' <= time[1] && time[1] <= '9') ? '1' : '2';
    }
    if (time[1] == '?') {
        time[1] = (time[0] == '2') ? '3' : '9';
    }
    if (time[3] == '?') {
        time[3] = '5';
    }
    if (time[4] == '?') {
        time[4] = '9';
    }
    return time;
}

int main() {
    char time[] ="2?:?0";
    cout << "time=" << time << endl;

    cout << "max time=" << maximumTime(time);
    return 0;
}

输出结果


time=2?:?0
max time=23:50

返回顶部